import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class _239滑动窗口最大值 {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        int[] r =new int [length-k+1];
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0]-o1[0];
            }
        });
        for (int i = 0; i < k; i++) {
            q.offer(new int[]{nums[i],i});
        }
        r[0] = q.peek()[0];

        //3-8 
        for (int i = k; i < length; i++) {
            q.offer(new int[]{nums[i],i});
            while (q.peek()[1]<=i-k) {
                q.poll();
            }
            r[i-k+1]=q.peek()[0];
        }
        return r;
    }

    public static void main(String[] args) {
        System.out.println();
        // Arrays.stream(maxSlidingWindow2(new int[]{1,3,-1,-3,5,3,6,7}, 3)).forEach(System.out::println);
        System.out.println();
        // Arrays.stream(maxSlidingWindow2(new int[]{1,-1}, 1)).forEach(System.out::println);
        Arrays.stream(maxSlidingWindow(new int[]{10,9,8,7,6,5,4,3,2,1,0}, 3)).forEach(System.out::println);
        
    }


    // public static int[] maxSlidingWindow2(int[] nums, int k) {
        // int length = nums.length;
        // int[] r =new int [length-k+1];
        // Deque<Integer> deque = new LinkedList<Integer>();
        // for (int i = 0; i < k; ++i) {
        //     while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
        //         deque.pollLast();
        //     }
        //     deque.offerLast(i);
        // }
        // r[0] = nums[deque.peekFirst()];
        // for (int i = k; i < length; ++i) {
        //     while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
        //         deque.pollLast();
        //     }
        //     deque.offerLast(i);
        //     while (deque.peekFirst() <= i - k) {
        //         deque.pollFirst();
        //     }
        //     r[i - k + 1] = nums[deque.peekFirst()];
        // }
        // return r;
    // }
}
